// https://leetcode-cn.com/problems/word-break/submissions/
class TrieNode {
public:
    TrieNode* children[26];
    bool isWord;
    TrieNode () {
        for (int i = 0; i < 26; ++i) {
            children[i] = NULL;
        }
        isWord = false;
    }
};

class Trie {
public:
    TrieNode *root;
    Trie() {
        root = new TrieNode;
    }    
    void build(vector<string>& wordDict) {
        for (int i = 0; i < wordDict.size(); ++i) {
            insert(wordDict[i]);
        }
    }
    void insert(string& word) {
        TrieNode* t = root;
        for (int j = 0; j < word.size(); ++j) {
            if (!t->children[word[j] - 'a']) {
                t->children[word[j] - 'a'] = new TrieNode();
            }
            t = t->children[word[j] - 'a'];
        }
        t->isWord = true;
    }
    bool search(string& word) {
        TrieNode *t = root;
        for (int i = 0; i < word.size(); ++i) {
            if (!t->children[word[i] - 'a']) return false;
            t = t->children[word[i] - 'a'];
        }
        return t->isWord;
    }
};

class Solution {
public:
    // 法一:划分型dp
    // bool wordBreak(string s, vector<string>& wordDict) {
    //     int n = s.length();
    //     vector<bool> rec(n + 1, false);
    //     rec[0] = true; //注意！！！
    //     // unordered_set<string> dict(wordDict.begin(), wordDict.end());
    //     Trie dict;
    //     dict.build(wordDict); 
    //     for (int i = 0; i <= n; ++i) {
    //         for (int j = 0; j < i; ++j) {
    //             // string tmp = s.substr(j + 1, i - j - 1); 注意刚好是从j开始
    //             string tmp = s.substr(j, i - j);
    //             // rec[i] = rec[i] || (rec[j] && (dict.find(tmp) != dict.end()));
    //             // if (rec[j] && dict.find(tmp) != dict.end()) {
    //             if (rec[j] && dict.search(tmp)) {
    //                 rec[i] = true;
    //                 break; // 剪枝
    //             }
    //         }
    //     }
    //     return rec.back();
    // }

    // 法二：转换为背包问题（适用于字典小的情况）
    // 组合背包（有顺序，可重复取）：外层正序循环背包，内层循环物品
    // bool wordBreak(string s, vector<string>& wordDict) {
    //     int n = s.size();
    //     vector<bool> rec(n + 1);
    //     rec[0] = true; 
    //     for (int i = 1; i <= n; ++i) {
    //         for (int j = 0; j < wordDict.size(); ++j) {
    //             int len = wordDict[j].size();
    //             if (i >= len && wordDict[j] == s.substr(i - len, len)) 
    //                 rec[i] = rec[i] || rec[i - len];
    //         }
    //     }
    //     return rec.back();
    // }
};

// 法三：DFS TLE
// class Solution {
// public:
//     bool helper(string s, vector<string>& wordDict) {
//         for (int i = s.size(); i >= 0; --i) {
//             string tmp = s.substr(0, i);
//             if (find(wordDict.begin(), wordDict.end(), tmp) != wordDict.end()) {
//                 if (i == s.size() || helper(s.substr(i), wordDict)) return true;
//             }
//         }
//         return false;
//     }
//     bool wordBreak(string s, vector<string>& wordDict) {
//         return helper(s, wordDict);
//     }
// };

// DFS + Trie TLE
// class Solution {
// public:
//     bool helper(string s, Trie trie) {
//         for (int i = s.size(); i >= 0; --i) {
//             string tmp = s.substr(0, i);
//             if (trie.search(tmp)) {
//                 if (i == s.size() || helper(s.substr(i), trie)) return true;
//             }
//         }
//         return false;
//     }
//     bool wordBreak(string s, vector<string>& wordDict) {
//         Trie trie;
//         trie.build(wordDict);
//         return helper(s, trie);
//     }
// };

// DFS + Trie + Memo（记忆化）
class Solution {
public:
    bool helper(string s, int start, Trie trie, vector<int>& memo) {
        if (memo[start] != -1) return memo[start];
        for (int i = s.size(); i >= start; --i) {
            string tmp = s.substr(start, i - start);
            if (trie.search(tmp))  {
                // if (i == s.size() || helper(s.substr(i), i, trie, memo)) { 注意！！
                if (i == s.size() || helper(s, i, trie, memo)) {
                    memo[start] = 1;
                    return true;
                }
            }
        }
        memo[start] = 0;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        Trie trie;
        trie.build(wordDict);
        vector<int> memo(s.size(), -1);
        return helper(s, 0, trie, memo);
    }
};

class Solution {
public:
    // 法四：BFS   个：BFS其实和dp有点类似，只是需要额外加记忆化
    bool wordBreak(string s, vector<string>& wordDict) {
        queue<int> q;
        q.push(0);
        vector<bool> visited(s.size(), false);
        visited[0] = true;
        while (!q.empty()) {
            int len = q.size();
            for (int i = 0; i < len; ++i) {
                int tmp = q.front();
                q.pop();
                for (auto& w: wordDict) {
                    if (s.substr(tmp, w.size()) == w) {
                        int new_start = tmp + w.size();
                        if (new_start > s.length() || visited[new_start]) continue;
                        if (new_start == s.length()) return true;
                        q.push(new_start);
                        visited[new_start] = true;
                    }
                }
            }
        }
        return false;
    }
};